from queue import PriorityQueue
import numpy as np

# begin_str = '2 8 3 1 0 4 7 6 5'
# target_str = '1 2 3 8 0 4 7 6 5'
# begin = np.array(list(map(int, begin_str.strip(' ').split(' ')))).reshape(3, 3)
# target = np.array(list(map(int, target_str.strip(' ').split(' ')))).reshape(3, 3)
begin = np.array(list(map(int, input('输入初始状态：').strip(' ').split(' ')))).reshape(3, 3)
target = np.array(list(map(int, input('输入目标状态：').strip(' ').split(' ')))).reshape(3, 3)
print('====================')
print('初始状态：\n', begin)
print('--------------------')
print('目标状态：\n', target)
print('====================')

# 定义OPEN表与CLOSED表
open_list = PriorityQueue()  # 使用PriorityQueue类型，便于得到具有最小f值的节点
open_matrix_list = []  # 单独存储状态矩阵，便于检查状态是否存在于OPEN表中
closed_list = []
closed_matrix_list = []  # 同理open_matrix_list

flag = True  # 用于记录成功与否
step = 0  # 用于搜索记录步数


class Node:
    def __init__(self, matrix, d, parent=None):
        self.matrix = matrix  # 表示当前状态的矩阵
        self.d = d  # 当前步数
        self.h = self.get_h()
        self.f = self.d + self.h
        self.parent = parent

    def __lt__(self, other):
        return self.f < other.f

    def __eq__(self, other):
        return self.f == other.f

    def get_h(self):
        dist = 0  # 用于保存所有数码与其目标位置之间曼哈顿距离的总和
        for row in self.matrix:
            for item in row:  # 遍历当前矩阵
                if item == 0:  # 排除0号空数码
                    continue
                # 分别求得当前数码所在位置与其目标位置的坐标
                item_coordinate = np.where(self.matrix == item)
                target_coordinate = np.where(target == item)
                # 求当前数码与目标的曼哈顿距离，并将其与dist相加
                dist += np.abs(item_coordinate[0][0] - target_coordinate[0][0])
                dist += np.abs(item_coordinate[1][0] - target_coordinate[1][0])
        return dist


def m_in_list(m, m_list):  # 用于判断矩阵是否在list中
    for item in m_list:
        if (m == item).all():
            return True
    return False


def get_index(m, m_list):  # 用于得到矩阵在list中的索引值
    index = 0
    for item in m_list:
        if (m == item).all():
            return index
        index += 1
    return None


def get_successor(node):
    successors = []  # 用于存储后续节点

    zero_coordinate = np.where(node.matrix == 0)  # 获得空数码位置坐标
    x = zero_coordinate[0][0]
    y = zero_coordinate[1][0]

    # 分情况求得x_next、y_next
    if x == 0:
        x_next = [x, x + 1]
    elif x == 1:
        x_next = [x - 1, x, x + 1]
    else:
        x_next = [x - 1, x]
    if y == 0:
        y_next = [y, y + 1]
    elif y == 1:
        y_next = [y - 1, y, y + 1]
    else:
        y_next = [y - 1, y]

    # 计算得到各后续节点状态矩阵，得到后续节点列表
    for x_item in x_next:
        for y_item in y_next:
            if abs(x_item - x) == 1 and abs(y_item - y) == 1:
                continue
            if x_item == x and y_item == y:
                continue
            matrix_next = node.matrix.copy()
            matrix_next[x][y], matrix_next[x_item][y_item] = matrix_next[x_item][y_item], matrix_next[x][y]
            successors.append(matrix_next)
    return successors


begin_node = Node(begin, 0)
open_list.put(begin_node)
open_matrix_list.append(begin_node.matrix)

print('开始搜索！')
print('====================')
while True:
    while True:
        if open_list.empty():
            print('未找到路径！')
            flag = False
            break

        best_node = open_list.get()
        if m_in_list(best_node.matrix, open_matrix_list):  # 若不在open_matrix_list中说明当前节点已被经过
            break
    if not flag:
        break

    del open_matrix_list[get_index(best_node.matrix, open_matrix_list)]
    closed_list.append(best_node)
    closed_matrix_list.append(best_node.matrix)

    print('Step:', step)
    print(best_node.matrix)
    print('d:' + str(best_node.d), 'h:' + str(best_node.h), 'f:' + str(best_node.f))
    print('--------------------')

    if (best_node.matrix == target).all():
        print('到达目标状态，搜索结束！')
        print('总步数:', step)
        break

    successor_list = get_successor(best_node)
    for matrix_next in successor_list:
        next_node = Node(matrix_next, best_node.d + 1, best_node)
        if m_in_list(matrix_next, open_matrix_list):
            open_list.put(next_node)  # 直接将新节点加入open_list表中，之后只需判断该节点状态矩阵是否在CLOSED表中即可确定是否已经过
        elif m_in_list(matrix_next, closed_matrix_list):
            old_node = closed_list[get_index(matrix_next, closed_matrix_list)]
            if next_node.d < old_node.d:
                closed_list[get_index(matrix_next, closed_matrix_list)] = next_node  # 将旧节点替换为新节点
        else:
            open_list.put(next_node)
            open_matrix_list.append(matrix_next)
    step += 1
